1. Field of the Invention
The present invention relates to a technology for specifying a cause of occurrence of multiple hits with a small-scale and simple configuration in a content addressable memory (CAM).
2. Description of the Related Art
FIG. 17 is a block diagram of an application example of a conventional cache memory device 11. The cache memory device 11 is a storage device, for example, a CAM device used to compensate for a speed difference between a central processing unit (CPU) 10 and a main memory 13. The CAM mentioned here is a memory in which a location of data stored in a memory area is indicated not by an address but by a content.
The CPU 10 accesses the cache memory device 11 or the main memory 13 to perform data read/write.
The main memory 13 has such characteristics that it has a large capacity and access time is slow as compared with that of the cache memory device 11. As shown in FIG. 18, the main memory 13 stores all the data used in the CPU 10.
More specifically, the main memory 13 stores 64-bit data<63:0> coupled to respective 64-bit addresses<63:0> (0 bit to 63 bits).
Referring back to FIG. 17, the cache memory device 11 has characteristics such that the access time is short as compared with that of the main memory 13.
Furthermore, the storage capacity of the main memory 13 is larger than that of the cache memory device 11.
FIG. 19 is a diagram of the cache memory device 11 of FIG. 17. A tag random access memory (RAM) 12a stores up to 32 addresses <63:0> (see FIG. 18) at maximum, each as TAG<63:0> (tag) stored in the main memory 13.
A data RAM 12b also stores up to 32 data at maximum, each as DATA<63:0>, coupled to the respective tags TAG<63:0> stored in the tag RAM 12a. 
More specifically, the tag RAM 12a has Entries 0 to 31 as memory locations. The address<63:0> (see FIG. 18) stored in the main memory 13 as TAG<63:0> (tag) is stored in each of the Entries 0 to 31.
Similarly to the tag RAM 12a, the data RAM 12b also has Entries 0 to 31 as memory locations. The Entries 0 to 31 of the tag RAM 12a are coupled to the respective Entries 0 to 31 of the data RAM 12b. 
Respectively stored in the Entries 0 to 31 of the data RAM 12b are data<63:0> (see FIG. 18) that are stored in the main memory 13, each as DATA<63:0>.
Comparators 200 to 2031 are provided corresponding to the respective Entries 0 to 31 of the tag RAM 12a, and each of them compares a 64-bit search address “ACCS_ADRS <63:0>” output from the CPU 10 (see FIG. 17) with a tag “TAG<63:0>” stored in each of the Entries 0 to 31. If the search address and the tag coincide with each other, a relevant comparator outputs the result of comparison indicating tag hit as “TAG_HIT”.
During normal operation, any one of the comparators 200 to 2031 outputs one TAG_HIT (tag hit).
However, when the same TAG<63:0> (tag) is stored in a plurality of entries of the tag RAM 12a, the TAG_HIT (tag hit) is output from the comparators, and it is thereby determined as a multi-hit error. When the multi-hit error occurs, the comparators 200 to 2031 output the result of determination indicating multiple hits as “MULTI-HIT”.
A selector 30 selects DATA<63:0> (data) stored in an entry corresponding to the TAG_HIT (tag hit), out of DATA<63:0> (data) stored in the respective Entries 0 to 31 of the data RAM 12b, and outputs the data selected.
The data “DATA<63:0>” output from the selector 30 is the search result corresponding to the search address “ACCS_ADRS <63:0>”, and is input to the CPU 10.
Referring to FIG. 19, it is necessary to check an error due to bit reversed or the like on the tags TAG<63:0> stored in the Entries 0 to 31 of the tag RAM 12a. 
FIG. 20 is a diagram of a cache memory device 40 having a parity check function as a function for the check. In FIG. 20, the same reference numerals are assigned to those corresponding to the portions of FIG. 19.
A selector 41 and a parity check unit 42 are newly provided in the configuration of FIG. 20. The selector 41 selects a tag TAG<63:0> stored in an entry corresponding to the TAG_HIT (tag hit), out of the tags TAG<63:0> stored in the respective Entries 0 to 31 of the tag RAM 12a, and outputs the tag.
The parity check mentioned here indicates checking using a parity bit whether there is any error (bit is reversed or so) in data. To perform a parity check, a parity bit (0 or 1) is previously added to original data to be checked so that the number of “1” becomes an even number.
Furthermore, the parity check is performed in the following manner. That is, if the number of “1” is the even number, then it is determined that no error occurs, but if the number of “1” is an odd number, then it is determined that a parity error occurs due to a bit reversed or so.
For example, when the original data has an 8-bit structure such as “00101000”, the number of “1” is the even number, and hence, a parity bit of “0” is added to the structure to be a 9-bit structure such as “00101000”+“0”.
If “00101000”+“0” is changed to “10101000”+“0” due to the bit reversed or so, the number of “1” is an odd number (=3), and hence, it is determined that the parity error occurs.
When the original data has an 8-bit structure such as “00101100”, the number of “1” is an odd number, and hence, a parity bit of “1” is added to be a 9-bit structure such as “00101100”+“1”.
If “00101100”+“1” is changed to “10101100”+“1” due to a bit reversed or so, the number of “1” is an odd number (=5), and hence, it is determined that the parity error occurs.
In the cache memory device 40 of FIG. 20, each of the Entries 0 to 31 of the tag RAM 12a stores the tag TAG<63:0> and a parity bit “TAG_P<7:0>”.
The parity check unit 42 executes a parity check to TAG<63:0> (tag) selected by the selector 41. If a parity check error occurs, the parity check unit 42 outputs the result of check indicating a party check error as “TAG_PE”. When the TAG_PE (party check error) is output, the DATA<63:0> (data) selected by the selector 30 is made invalid.
However, in the cache memory device 40 shown in FIG. 20, when multiple hits MULTI-HIT occur, a cause (and the following first cause and second cause) of the multiple hits cannot be uniquely identified.
More specifically, the first cause of the multiple hits includes a case where the same tag TAG<63:0> is simply stored in the entries of the tag RAM 12a to cause MULTI-HIT (multiple hits).
The second cause includes a case where different tags TAG<63:0> are stored in the entries of the tag RAM 12a, but the two tags TAG<63:0> are determined as the same tag TAG<63:0> due to the error such as a bit reversed, to cause MULTI-HIT (multiple hits).
To resolve the problems in the conventional technology, as shown in a cache memory device 50 of FIG. 21, parity check (PC) units 510 to 5131 are provided corresponding to the respective Entries 0 to 31 of the tag RAM 12a, and the parity check is executed for each entry.
However, in the cache memory device 50, the parity check units 510 to 5131, which perform parity checks on 64 bits for 32 entries, respectively, cause an increased circuit scale and a complicated configuration.
Patent Document 1: Japanese Patent Application Laid-Open No. H8-95856.